package jianzhioffer;

/**
 * 无符号数 二进制中1的个数
 * 其中，负数用补码表示
 *
 * 题解参考:https://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html
 *
 * Created by yzy on 2020-06-04 15:27
 */
public class NumberOf1 {

    public static void main(String[] args) {
        int n = 14567;
        System.out.println(numberOf1(n));
        System.out.println(numberOf1Quick(n));
    }


    /**
     * 这个方法超时了
     * @param n
     * @return
     */
    public static int numberOf1(int n) {
        int num = 0;
        while(n != 0){
            if((n&1) == 1){
                num++;
            }
            n = n>>1;
        }
        return num;
    }


    /**
     * 17ms, 9296KB
     *
     * 思路：
     * 【该方法无关正负号，都适用】
     * n 和 (n-1) 相与的结果，是可以把n的二进数后面，最后一个1之前的0都消除掉。
     * 一直执行，最终会得到0.
     * 所以，能相与几次，代表数字后有几个1。
     *
     * @param n
     * @return
     */
    public static int numberOf1Quick(int n) {
        int num = 0;
        while(n != 0){
            n = n & (n-1);
            num++;
        }
        return num;
    }
}
